package com.fe.class09;

import java.util.Stack;

/**
 * @Description 给定一个单链表的头节点head，请判断该链表是否为回文结构。
 * 1）堆栈方法特别简单（笔试用）
 * 2）改原链表的方法就需要注意边界了（面试用）
 * @Author sosuke :-)
 * @Date 2022/1/25 22:46
 */
public class Code02_PalindromeLinkedList {

    public static class Node {
        private int value;
        private Node next;

        public Node(int value) {
            this.value = value;
        }
    }

    /**
     * 使用栈来实现，空间复杂度O(n)
     * 链表全部入栈后再依次出栈，并和链表依次比较，相等则为回文结构
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome01(Node head) {
        // 入栈
        Stack<Node> stack = new Stack<>();
        Node cur = head;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        // 出栈
        while (head != null && !stack.isEmpty()) {
            if (stack.pop().value != head.value) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

    /**
     * 使用栈来实现，空间复杂度O(n/2)
     * 链表后半部分入栈后再依次出栈，并和链表依次比较，相等则为回文结构
     * 找后半部分：奇数长度返回中点后一个，偶数长度返回下中点
     * @param head
     * @return
     */
    public static boolean isPalindrome02(Node head) {
        // 节点数0、1
        if (head == null || head.next == null) {
            return true;
        }
        // 节点数>=2
        // head、cur--->right
        Node right = head.next; // 表示要找的后半部分头节点：奇数长度返回中点后一个，偶数长度返回下中点
        Node cur = head;
        while (cur.next != null && cur.next.next != null) {
            right = right.next;
            cur = cur.next.next;
        }
        // 后半部分入栈
        Stack<Node> stack = new Stack<>();
        while (right != null) {
            stack.push(right);
            right = right.next;
        }
        // 后半部分出栈，逐个比较
        while (!stack.isEmpty()) {
            if (stack.pop().value != head.value) {
                return false;
            }
            head = head.next;
        }

        return true;
    }

    /**
     * 不使用容器方式，仅使用有限变量，空间复杂度O(1)
     * 1. 找链表中点或者上中点，统称为中点
     * 2. 从中点开始往后的链表进行单链表逆序，并返回逆序后的头节点
     * 3. 从两头往中间逐个比较
     * 4. 将链表后半部分恢复原状
     */
    public static boolean isPalindrome03(Node head) {
        // 节点数0、1
        if (head == null || head.next == null) {
            return true;
        }
        // 节点数>=2
        // head、slow、fast---->node
        Node n1 = head;
        Node n2 = head;
        while (n2.next != null && n2.next.next != null) {
            n1 = n1.next;
            n2 = n2.next.next;
        }

        // 此时n1为中点或上中点，从中点n1开始要进行链表逆序(n1为头节点)
        // 逆序完成后，n3为逆序后的头节点，n1 = null,n2 = null
        Node n3 = null;
        while (n1 != null) {
            n2 = n1.next;
            n1.next = n3;
            n3 = n1;
            n1 = n2;
        }

        n1 = n3; // 保存链表最后一个节点
        n2 = head; // n2为左侧头节点，n3为右侧逆序的头节点
        boolean ans = true;
        // 逐个比较，发现不一致时，不能return，要break，后续还要恢复链表
        while (n1 != null && n2 != null) {
            if (n1.value != n2.value) {
                ans = false;
                break;
            }
            n1 = n1.next; // 向左移动
            n2 = n2.next; // 向右移动
        }

        // 从n3开始要进行链表逆序（n3为头节点）
        n1 = null;
        while (n3 != null) {
            n2 = n3.next;
            n3.next = n1;
            n1 = n3;
            n3 = n2;
        }
        return ans;
    }

    public static void main(String[] args) {
        int testTime = 100000;
        int maxSize = 15;
        int maxValue = 100;
        for (int i = 0; i < testTime; i++) {
            Node node = generateRandomLinkedList(maxSize, maxValue);
            if (isPalindrome01(node) != isPalindrome02(node) ||
                    isPalindrome02(node) != isPalindrome03(node) ||
                    isPalindrome01(node) != isPalindrome03(node)) {
                System.out.println("Fuck");
                printLinkedList(node);
                System.out.println("ans1 = " + isPalindrome01(node));
                System.out.println("ans2 = " + isPalindrome02(node));
                System.out.println("ans3 = " + isPalindrome03(node));
                return;
            }
            if (isPalindrome01(node)) {
                printLinkedList(node);
            }
        }

        System.out.println("Nice");
        Node node = generateRandomLinkedList(maxSize, maxValue);
        printLinkedList(node);
        System.out.println("ans1 = " + isPalindrome01(node));
        System.out.println("ans2 = " + isPalindrome02(node));
        System.out.println("ans3 = " + isPalindrome03(node));
        printLinkedList(node);
    }

    /**
     * 随机生成单链表
     *
     * @return
     */
    public static Node generateRandomLinkedList(int maxSize, int maxValue) {
        // [0,maxSize] + 4
        int size = (int) (Math.random() * (maxSize + 1)) + 4;
        // if (size == 0) return null;
        Node head = new Node((int) (Math.random() * (maxValue + 1)));
        size--;
        Node pre = head;
        for (int i = 0; i < size; i++) {
            Node next = new Node((int) (Math.random() * (maxValue + 1)));
            pre.next = next;
            pre = next;
        }
        return head;
    }

    /**
     * 打印单链表
     *
     * @param head
     */
    public static void printLinkedList(Node head) {
        if (null == head) {
            System.out.println("\"null\"");
            return;
        }
        Node cur = head;
        while (null != cur) {
            System.out.print(cur.value + "--->");
            System.out.print(cur.next == null ? "null" : "");
            cur = cur.next;
        }
        System.out.println();
    }

}
